package com.example.leetcode.c101_c200.c143;
/**
 * 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
 * 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 示例 1:
 *
 * 给定链表 1->2->3->4, 重新排列为 1->4->2->3.
 * 示例 2:
 *
 * 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reorder-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import com.example.leetcode.common.ListNode;
import com.example.leetcode.common.ListNodeWrapper;

/**
 * 重排链表
 * @author zhanpengguo
 * @date 2020-10-20 8:22
 */
public class Solution {

    /**
     * 1、找出中间节点
     * 2、旋转后半链表
     * 3、前半链表和旋转后的后半链表合并
     * @param head
     */
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode middle = getMiddle(head);
        ListNode hou = middle.next;
        middle.next = null;
        ListNode reverse = reverser(hou);
        merge(head,reverse);
    }

    private ListNode getMiddle(ListNode head) {
        ListNode next = head.next;
        while (next != null && next.next != null) {
            head = head.next;
            next = next.next.next;
        }
        return head;
    }

    private ListNode reverser(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    private void merge(ListNode l1, ListNode l2) {
        ListNode temp1, temp2;
        while (l1 != null && l2 != null) {
            temp1 = l1.next;
            temp2 = l2.next;
            l1.next = l2;
            l1 = temp1;
            l2.next = l1;
            l2 = temp2;
        }
    }

    public static void main(String[] args) {
        ListNode head = ListNodeWrapper.stringToListNode("[1,2,3,4,5]");
        Solution solution = new Solution();
        solution.reorderList(head);
        ListNodeWrapper.prettyPrintLinkedList(head);
    }

}
